package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
        Solution solution = new Solution();

        System.out.println("=== 粉刷房子测试 ===");
        
        // 测试用例1: 3个房子
        int[][] costs1 = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
        System.out.println("测试1 - 3个房子:");
        System.out.println("成本矩阵: [[17,2,17], [16,16,5], [14,3,19]]");
        System.out.println("最小成本: " + solution.minCost(costs1)); // 输出: 10 (红->绿->绿: 2+5+3=10)
        
        // 测试用例2: 2个房子
        int[][] costs2 = {{7, 6, 2}, {8, 4, 5}};
        System.out.println("\n测试2 - 2个房子:");
        System.out.println("成本矩阵: [[7,6,2], [8,4,5]]");
        System.out.println("最小成本: " + solution.minCost(costs2)); // 输出: 6 (蓝->绿: 2+4=6)
        
        // 测试用例3: 单个房子
        int[][] costs3 = {{5, 8, 3}};
        System.out.println("\n测试3 - 1个房子:");
        System.out.println("成本矩阵: [[5,8,3]]");
        System.out.println("最小成本: " + solution.minCost(costs3)); // 输出: 3
        
        // 测试用例4: 4个房子
        int[][] costs4 = {{3, 5, 3}, {6, 17, 6}, {7, 13, 18}, {9, 10, 18}};
        System.out.println("\n测试4 - 4个房子:");
        System.out.println("成本矩阵: [[3,5,3], [6,17,6], [7,13,18], [9,10,18]]");
        System.out.println("最小成本: " + solution.minCost(costs4)); // 输出: 26
    }

    // 粉刷房子
    static class Solution {
        public int minCost(int[][] costs) {
            // 1) 获取房子数量
            int m = costs.length;
            // dp[i][j] 表示粉刷前 i 个房子，第 i 个房子颜色为 j 的最小成本
            int[][] dp = new int[m + 1][3];

            // 2) 从第1个房子开始遍历到第m个房子
            for (int i = 1; i <= m; i++) {
                // 当前房子涂颜色0，从上一个房子的颜色1或2中选最小的
                dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
            }

            // 3) 返回最后一个房子三种颜色中的最小成本
            return Math.min(dp[m][0], Math.min(dp[m][1], dp[m][2]));
        }
    }
}